" Enumeration Complexity: Incremental Time, Delay and Space" par YANN STROZECKI

Résumé :
Lister un ensemble de solutions est un problème courant en informatique, que ça soit pour les compter, pour trouver un élément optimal, ou constituer une librairie d’objets intéressants. Il existe plusieurs mesures de complexité spécifiques à l’énumération : le temps pour générer toutes les solutions, le temps pour en générer un nombre donné ou temps incrémental et le délai entre la production de deux solutions successives. De nombreuses classes de complexité peuvent ensuite être définies en bornant ces mesures ainsi que l’espace utilisé par une fonction de la taille de l’entrée et de la sortie. On considère généralement qu’un problème est résoluble efficacement s’il est en temps incrémental polynomial ou en délai polynomial. Nous montrons comment séparer ces classes, mais aussi que le délai polynomial et temps incrémental linéaire coïncident, même en se restreignant à un espace polynomial. Pour des familles de problèmes comme la saturation d’ensembles, l’interpolation de polynômes, ou les requêtes du second ordre, nous explorons précisément la frontière entre délai polynomial et temps incrémental polynomial en donnant des algorithmes et des bornes inférieures. Puis nous proposons des notions de faisabilité plus fortes et adaptées à la pratique comme le délai polynomial fort, illustré sur le problème de génération des modèles d’une formule DNF, la représentation compacte ou l’approximation de l’ensemble des solutions à énumérer.
Abstract:

Listing the elements of a set is a common problem in computer science, either to count them, or to find the optimal element or to build a library of interesting objects. There are several complexity measures specific to enumeration: the time to generate all solutions, the time to generate a given number of solutions or incremental time and the delay between two consecutive solutions. Many classes can then be defined by bounding these measures and the memory used by functions of the size of the input and of the output. Tractability is generally understood as being solved in polynomial incremental time or polynomial delay. We show a strict inclusion of these classes but also that linear incremental time and polynomial delay coincide even when the memory is polynomially bounded. For families of problems, such as set saturation, polynomial interpolation or second order queries, we investigate the boundary between polynomial delay and polynomial incremental time through the design of efficient algorithms and lower bounds. We then propose stronger notions of tractability: strong polynomial delay, illustrated by the study of the generation of models of a DNF formula, compact representation of the solution set or approximation of the solution set.